package dynamicProgramming;

/**
 * @author zxc
 * @date 2023/01/29 09:07
 **/

/**
 * 题目 ：正则表达式匹配
 * 题目详述 ：
 * 给你一个字符串s和一个字符规律p，请你来实现一个支持 '.'和'*'的正则表达式匹配。
 * '.' 匹配任意单个字符
 * '*' 匹配零个或多个前面的那一个元素
 * 所谓匹配，是要涵盖整个字符串s的，而不是部分字符串。
 *
 * 提示：
 * 1 <= s.length<= 20
 * 1 <= p.length<= 30
 * s只包含从a-z的小写字母。
 * p只包含从a-z的小写字母，以及字符.和*。
 * 保证每次出现字符* 时，前面都匹配到有效的字符
 */
public class IsMatch {
    public static void main(String[] args) {
        System.out.println(isMatch("aaa" , "ab*a*c*a"));
    }
    /**
     * 思路 ：
     * 假设f(i,j)为字符串s前i个字符根据字符规律p的前j个字符是否能够尽心匹配;
     *
     * 状态转移方程 ：
     * （1）若是字符规律p中第j个字符为 '字母'的话，
     * a.s[i] == p[j]情况下,即f(i,j) = f(i-1,j-1);
     * b.s[i] != p[j]情况下，即f(i,j) = false;
     * （2）若是字符规律p中第j个字符为 '.'的话，
     * ===》 由于字符'.'能够匹配任意单个字符，所以f(i,j) = f(i-1,j-1);
     * （3）若是字符规律中第j个字符为 '*'的话，
     * a.p[j-1] != s[j]情况下，即'p[j-1]*'组合并不能够匹配到s[i]，直接丢弃'p[j-1]*'组合即可;
     * ===> f(i,j) = f(i,j-2);
     * b.p[j-1] == s[i.....]情况下，即'p[j-1]*'组合能够匹配到s[i......];
     * ===> f(i,j) = f(i-1,j);
     * @param s
     * @param p
     * @return
     */
    public static boolean isMatch(String s, String p) {
        // 假设f(i,j)为长度为j的匹配规则能够匹配到长度为i的字符串s;
        // 辅助数组dp，用来存储计算结果;
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        // 特殊情况1 ：空字符串s和空字符规律p之间能够进行相互匹配;
        // 特殊情况3 ：若是匹配规律p为空的话，同时主字符串 != null,则f(i,0) == false;
        // 1.当匹配规律为空的时候，除非字符串是也为空（即，f(0,0) == true;），否则f(i,0) == false;
        dp[0][0] = true;
        // 特殊情况2 ：主字符串s为空的话，同时匹配规律为(字符*...)，则f(0,j) == true;
        // 2.当主字符串为空 && 匹配规律不为空的时候，若是匹配规律允许空字符串的话，则f(0,j) == true;
        for(int j = 0 ; j < p.length() ; j++){
            // 即，在主字符串s为空的情况下，若是匹配规律p允许匹配空字符串的话，则f(0,j) == true;
            if(p.charAt(j) == '*'){
                dp[0][j + 1] = dp[0][j - 1];
            }
            else {
                dp[0][j + 1] = false;
            }
            System.out.print(dp[0][j + 1] + " ");
        }
        System.out.println("");

        // 遍历主字符串 && 匹配规则p
        for(int i = 0 ; i < s.length() ; i++){
            for(int j = 0 ; j < p.length() ; j++){
                // 3.即，在匹配规则的第j个字符不为'*';
                if(p.charAt(j) != '*'){
                    // 若是字符串s的最后一个字符 == 字符规律p的最后一个字符 / 字符规律p的最后一个字符为'.'的话，
                    // ===》 即，当字符规律p的最后一个字符不为'*'字符的话，同时满足与字符串s的最后一个字符相同，f(i,j) = f(i-1,j-1);
                    if(s.charAt(i) == p.charAt(j) || p.charAt(j) == '.'){
                        dp[i + 1][j + 1] = dp[i][j];
                    }
                    else {
                        // 若是匹配规则p的第j个字符与字符串s的第i个字符不相等时，即代表匹配不成功;
                        dp[i + 1][j + 1] = false;
                    }
                }
                /**
                 * 思考 ：为何要将'*'单独拎出来讨论？
                 * 解决 ：
                 * '字符*'可以表示零个/多个字符;
                 * ===》 可能会出现多种情况
                 * （1）'字符*'，表示一个/多个字符;
                 * （2）'字符*'，表示零个字符;
                 */
                else {
                    // 即，若是某个'字符*'组合之前的匹配规律已经能够匹配到字符串s，那么'字符*'组合就可有可无;
                    int k = 0;
                    // while循环所需要满足的条件 ：
                    // ===》 while循环，保证能够使得'字符*'能够匹配到尽可能多的字符;
                    //（1）主字符串s被遍历完之前（k <= i）;
                    //（2）匹配规则第j-1个字符 == 字符串s的第i...个字符 || 匹配规则第j-1个字符为'.';
                    //（3）若是dp[i+1][j+1] == true的话，则代表当前匹配规则p已经能够匹配到字符串;
                    while(!dp[i + 1][j + 1] && k <= i && (s.charAt(i - k) == p.charAt(j - 1) || p.charAt(j - 1) == '.')){
                        // （1）匹配到一个字符后，继续使用f(i,j+1)进行匹配;
                        // （2）不匹配任何字符（即，类似于匹配0个字符）,直接使用f(i+1,j-1)进行匹配;
                        dp[i + 1][j + 1] = dp[i - k][j + 1] || dp[i + 1 - k][j - 1];
                        k++;
                    }
                    // 若是dp[i+1][j+1] == false的话，则代表当前匹配规则p还未能够匹配到字符串
                    if(!dp[i + 1][j + 1]){
                        // （1）字符串s被遍历完的情况;
                        // （2）字符串s的第i个字符 != 匹配规则p的第j个字符;
                        int l = k > i ? 0 : i - k + 1;
                        dp[i + 1][j + 1] = dp[l][j - 1];
                    }
                }
                System.out.print(dp[i + 1][j + 1] + " ");
            }
            System.out.println("");
        }
        return dp[s.length()][p.length()];
    }
}
